package a10_动态规划;

import java.util.Scanner;

/**
 * <p>
 * a12_背包理论基础复习1
 * </p>
 *
 * @author flyduck
 * @since 2025/2/11
 */
public class a12_背包理论基础2复习1 {
    public static void main(String[] args) {
        ///////////////////////////////////////////////
//        Scanner scanner = new Scanner(System.in);
//        int number = scanner.nextInt();//几个物品
//        int totalWeight = scanner.nextInt();//总重量
//
//        int[] weightArray = new int[number];//每个物品的重量
//        int[] valueArray = new int[number];//每个物品的价值
//
//        for (int i = 0; i < number; i++) {
//            weightArray[i] = scanner.nextInt();
//        }
//
//        for (int i = 0; i < number; i++) {
//            valueArray[i] = scanner.nextInt();
//        }

        ///////////////////////////////////////////////

        //物品  重量  价值
        // 0     1    15
        // 1     3    20
        // 2     4    30

        //重量为4

        int number = 1;//几个物品
        int totalWeight = 10;//总重量

        int[] weightArray = new int[]{1};//每个物品的重量
        int[] valueArray = new int[]{10};//每个物品的价值

        //dp[j]含义：重量为j的背包存放的最大价值

        //初始化：dp[0] = 0;

        //递推公式：dp[j] = Math.max(dp[j],dp[j-weightArray[i]] + valueArray[i])

        int[] dp = new int[totalWeight+1];

        dp[0] = 0;

        for (int i = 0; i < number; i++) {
            for (int j = totalWeight; j >= 1; j--) {
                if(j >= weightArray[i]){
                    dp[j] = Math.max(dp[j],dp[j-weightArray[i]] + valueArray[i]);
                }
            }
        }

        System.out.println(dp[totalWeight]);
    }
}
